# 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 
# 
#  
# 
#  示例 1: 
# 
#  
# 输入: nums = [1,1,1,2,2,3], k = 2
# 输出: [1,2]
#  
# 
#  示例 2: 
# 
#  
# 输入: nums = [1], k = 1
# 输出: [1] 
# 
#  
# 
#  提示： 
# 
#  
#  1 <= nums.length <= 10⁵ 
#  k 的取值范围是 [1, 数组中不相同的元素的个数] 
#  题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的 
#  
# 
#  
# 
#  进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。 
# 
#  Related Topics 数组 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列） 👍 1967 👎 0
from collections import Counter
from typing import List
import heapq


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 时间复杂度：O(n+klogn)
        # d = {}
        # re = []
        # for n in nums:
        #     if n in d:
        #         d[n][0] -= 1
        #     else:
        #         d[n] = [-1, n]
        #
        # q = list(d.values())
        # heapq.heapify(q)
        #
        # for i in range(k):
        #     p = heapq.heappop(q)
        #     re.append(p[1])
        # return re
        """
        方法二：如果数组的长度很长，把其放入堆是不合理的，所以我们把堆的大小控制在k
        :时间复杂度：O(n + m \log k)
        :param k:
        :return:
        """
        # 这个类内部实现实际上也是与方法1一样的构造字典
        freq_map = Counter(nums)
        q = []
        for num, freq in freq_map.items():
            heapq.heappush(q, (freq, num))
            if len(q) > k:
                # 如果堆的大小超过k，则移除栈顶（最小）的值
                heapq.heappop(q)
        # 因为是最小堆，故留下来的最后k个元素即为最大的
        return [num for freq, num in q]


# leetcode submit region end(Prohibit modification and deletion)
print(Solution().topKFrequent(nums=[1, 1, 1, 2, 2, 3, 3, 3, 3], k=2))
